﻿#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"

//堆的初始化
void HPInit(Heap* php)
{
	assert(php);
	php->arr = NULL;
	php->size = 0;
	php->capacity = 0;
}

//堆的销毁
void HPDestroy(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->size = 0;
	php->capacity = 0;
}

//判断数组否有空间或者空间够不够
void HPCheckCapacity(Heap* php)
{
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);
		assert(tmp);
		php->arr = tmp;
		php->capacity = newcapacity;
	}
}

//交换父子结点位置
void Swap(HPDataType* child, HPDataType* father)
{
	HPDataType tmp = *child;
	*child = *father;
	*father = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	while (child > 0)
	{
		int father = (child - 1) / 2;
		if (arr[child] < arr[father]) //不满足堆的要求，需要交换父子结点
		{
			Swap(&arr[child], &arr[father]);//由于要改变实参数组的数据，所以要地址传参
			child = father;
		}
		else //某次满足堆的条件即可跳出循环
		{
			break;
		}
	}
}

//堆的插入数据(向上调整算法)
void HPPush(Heap* php, HPDataType x)
{
	assert(php);
	HPCheckCapacity(php);

	php->arr[php->size] = x;
	php->size++;

	AdjustUp(php->arr, php->size - 1);
	//第二个形参传递的是数组的下标,需要注意
}

//向下调整算法
void AdjustDown(HPDataType* arr, int n)
{
	int father = 0;
	while (2 * father + 1 < n)
	//当一个父亲的左孩子下标超出当前堆最后一个数据下标时，也就是说这个父亲没有孩子，也就是说已经调整完成了
	{
		int leftchild = 2 * father + 1;
		int rightchild = 2 * father + 2;
		if (arr[father] > arr[leftchild] || (arr[father] > arr[rightchild] && rightchild < n))
		//如果父亲大于孩子则需要调整位置，如果是右孩子则还需要判断此时父亲是否还有右孩子
		{
			if (arr[leftchild] > arr[rightchild] && rightchild < n)
			//当左孩子较大时，父亲与右孩子进行交换，但是如果此时父亲没有右孩子则必须与左孩子交换
			{
				Swap(&arr[father], &arr[rightchild]);
				father = rightchild;
			}
			else
			{
				Swap(&arr[father], &arr[leftchild]);
				father = leftchild;
			}
		}
		else//只要当父亲同时小于两个孩子则调整完成了
		{
			break;
		}
	}
}

//堆的删除(向下调整算法)
void HPPop(Heap* php)
{
	assert(php);
	assert(php->size); //堆没有数据不能进行删除

	Swap(&(php->arr[0]), &(php->arr[php->size - 1]));
	php->size--; //这个代码相当于就是把数组尾部数据进行删除

	AdjustDown(php->arr, php->size);
}

//获取堆顶数据
HPDataType HPTop(Heap* php)
{
	assert(php);
	assert(php->size);

	return php->arr[0];
}

//堆判空
bool HPEmpty(Heap* php)
{
	assert(php);

	return php->size == 0;
}